In set theory, König’s theorem, due to Julius König (Hungarian: Gyula Kőnig), is a basic result in cardinal arithmetic. It uses the axiom of choice. It is not to be confused however with König's lemma?, another result of combinatorial set theory, but using instead the axiom of dependent choice (and due to the son, Dénes Kőnig).
(König) Let be the cardinality of a set . If for all , then .
Suppose we have proper inclusions . Choose basepoints and, letting be the product projection and the coproduct inclusion, define a map :
It is immediate that this is injective, and so .
Now we prove the last inequality is strict. Suppose to the contrary that there exists a surjective function . The function is not surjective, by the hypothesis . Thus for each we may choose such that . By supposition, there exists such that . But for some , whence , i.e., , and this contradicts how we chose .
One can see immediately how the axiom of choice enters the result: the product might be empty otherwise, hence could not satisfy the required inequality. In fact one can prove the axiom of choice from König’s theorem, in the form of “every product of a family of inhabited sets is inhabited”, by taking to be empty for each .
The following important corollary deserves to be called König’s corollary, since it is itself often referred to in the literature, but only ever as a follow-on from the above theorem. Note that we do not need to appeal to the full strength of König’s theorem to prove this corollary.
For any infinite cardinal , the cardinal has cofinality greater than .
We have . If is an increasing sequence with least upper bound , then we have surjection which immediately contradicts König’s theorem.
The appeal to the axiom of choice in the form discussed above is unnecessary, since is obviously inhabited. However, there are other ways in which choice-specific features make themselves known, for instance is a cardinal (i.e. has a well-ordering). And the statement that every infinite cardinal satisfies is equivalent to the axiom of choice. And lastly, the definition of cofinality is very difficult in the absence of AC, see for instance this blog post by Karagila.
However, it is possible to recover some of König’s theorem in the absence of the axiom of choice. For sets , , define to be the set of assignments which for each partial function specify an element . This set being nonempty imiplies a strong form of “there are no partial surjections ” (aka ), and the definition is as one might define using propositions as types. Conversely, if AC holds, then the is nonempty iff .
Given for each , then .
Let . We define a member as . Now, note that it can’t be the case that for any , , as then . This means that , as required.
Although the preconditions of the theorem are harder to attain, as is nonempty much less often than , it still holds in several useful cases:
The following conditions are each sufficient to construct an element of :
and an injection
and an injection
has a wellorder , and there is no partial surjection
An element and, for each total function , a specified
For , restricts to a partial function ( iff ), and gives an element of , so taking gives
For , extends to a partial function (defined as ), and , so take .
Immediate from and the above choiceless variant of König’s theorem, but can also be proven directly. Let be a partial function, and let . Then if , we have that iff , so , contradicting . Therefore, .
For , let . Then is uniquely defined as is wellordered and the set is nonempty (otherwise f is a partial surjection), and .
For , extend it to a total function by letting where defined and otherwise. Then , so let .
Last revised on July 20, 2021 at 15:07:48. See the history of this page for a list of all contributions to it.